package leetcode.recursive;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是
 * 回文串
 * 。返回 s 所有可能的分割方案。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "aab"
 * 输出：[["a","a","b"],["aa","b"]]
 * 示例 2：
 * <p>
 * 输入：s = "a"
 * 输出：[["a"]]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 16
 * s 仅由小写英文字母组成
 */

public class LeetCode131_Partition {
    public List<List<String>> partition(String s) {
        char[] arr = s.toCharArray();
        List<List<String>> r = new ArrayList<>();
        List<String> path = new ArrayList<>();

        f(0, arr, r, path);
        r.forEach(System.out::println);

        return r;
    }

    public void f(int curLen, char[] arr, List<List<String>> r, List<String> path) {
        if (curLen == arr.length) {
            // path为满足条件的结果
            r.add(new ArrayList<>(path));
        }

        for (int i = curLen; i < arr.length; i++) {
            String p = getSeg(curLen, i, arr);
            if (isOk(p)) {
                path.add(p);
                f(i + 1, arr, r, path);
                path.remove(path.size() - 1);
            }
        }
    }

    public String getSeg(int start, int end, char[] arr) {
        StringBuilder s = new StringBuilder();
        for (int i = start; i <= end; i++) {
            s.append(arr[i]);
        }
        return s.toString();
    }

    public boolean isOk(String s) {
        char[] ch = s.toCharArray();
        if (ch.length == 1) {
            return true;
        }

        int start = 0, end = ch.length - 1;
        while (start < end) {
            if (ch[start] != ch[end]) {
                return false;
            }
            start++;
            end--;
        }

        return true;
    }

    public static void main(String[] args) {
        LeetCode131_Partition leetCode131_partition = new LeetCode131_Partition();
        leetCode131_partition.partition("aab");
    }
}
